(1) Field of the Invention
The present invention relates to a traffic shaping apparatus, a communication node and a flow control method for sending out bandwidth controlled variable length frames.
(2) Description of Related Art
Recently, there is an increasing demand for high-speed networks such as broadband services. As one form of high-speed networks, Ethernet base networks that provide low cost communication have wide dissemination. In the Ethernet-base networks, best-effort based communication services in which an allocated bandwidth is determined subject to channel availability are provided, which is suitable for burst packet transmission with a high peak rate. However, a stable bandwidth per user is not guaranteed and temporary channel occupation by a particular user occurs. Thus, the best-effort based communication has such a problem that a stable quality service cannot be assured.
From network users, there is increasing demand for a high-quality communication service in which a minimum bandwidth is guaranteed. Provision of such a communication service is hoped for that a minimum guaranteed bandwidth determined by contract is stably assigned to every user and free bandwidth can be used effectively if occurs. Even if free bandwidth is available, when a packet transfer service exceeding a maximum allowed bandwidth set for each user in advance is performed, buffer overflow might occur at a receiving terminal and received data might be discarded. Therefore, a proper maximum allowed bandwidth should be set for each user and bandwidth must be controlled not to exceed it.
In transferring variable length frames as is done on Ethernet, since a bandwidth in use depends on both the number of frames (packets) and frame length, bandwidth per flow cannot be controlled with the control of the number of frames solely, like the fixed length cell transfer over an ATM network. Here, a frame (packet) denotes a data block comprising a header, payload, and a trailer as a unit of data transfer on a communication network.
As a prior art of variable length data transfer which ensures the minimum guaranteed bandwidth per flow and makes effective use of free bandwidth, a leaky bucket type bandwidth control using a leaky bucket model with a certain depth is known, as described in, e.g., Japanese Unexamined Patent Publication No. 2003-198611 (patent document 1). In the leaky packet based bandwidth control, the amount of water leaking out of the bucket per unit time is preset proportional to a target bandwidth and, when the water level of the bucket comes below than a preset threshold value, a buffer memory associated with the leaky bucket is given the right of transmission of frames. Each time a frame is sent out, the bucket water level is increased by an increment as much as the length of the sent frame. Thus, the amount of data transferred will fall within the range of the target bandwidth on an average.
In the prior art described in patent document 1, for each buffer memory (packet queue), a difference value between a level count value corresponding to the current leaky bucket water level and the threshold value which corresponds to a pre-specified minimum guaranteed bandwidth is stored. A packet queue from which a frame is output is selected so that a buffered packet (frame) is sent out in order from a buffer memory with the smallest difference value.
According to the above prior art, packets are output in order from a buffer memory that is the nearest to the minimum guaranteed bandwidth and, therefore, packet transfer can be performed in compliance with the minimum guaranteed bandwidth. Further, in calculation of a water level increment incidental to sending out of a packet, a variable increment value, which is increased according to decrease in the level count value indicating the current water level of the leaky bucket, can be used to increase stepwise a unit increment value by which the packet length is multiplied. By adopting the variable increment value, when a packet is sent out in a state that the level count value is greatly lower than the threshold value, the increase of the bucket water level can be accelerated for a quick return to a higher level than the threshold value.
In the above prior art, by setting two threshold values for the minimum guaranteed bandwidth and the maximum allowed bandwidth on the level counter, the level count value can be controlled not to fall outside the thresholds. Accordingly, sending out amount of packets exceeding the maximum allowed bandwidth does not occur in normal condition. However, if the level count value becomes greatly lower than the threshold value because of traffic disruption, temporarily sending out packets more than the maximum allowed bandwidth is possible to occur until the level count value returns to a level higher than the threshold value of the minimum guaranteed bandwidth, as will be described below.
FIG. 9A shows the order in which packets belonging to the same flow arrive. FIG. 9B shows the level count value of a leaky bucket. FIG. 9C shows timing at which each packet (frame) is output.
The level count value of the leaky bucket decreases at a rate in proportion to the target bandwidth as time elapses, as shown in FIG. 9B. Each time a packet is output, a value in accordance with the output packet length is added to the level count value. When the level count value becomes less than the threshold value TH, a packet can be output if an output line is in an idle state. In normal condition, by sending packets (P1, P2, P3) whenever the level count value has come to the threshold value TH, traffic shaping can be performed in compliance with the target bandwidth. However, for instance, in a situation where no packet to be sent exists because of disruption of packet arrival for a while or where the output line blocked state continues because of sending packets belonging to another flow (connection), the level count value will be greatly lower than the threshold value TH as shown a period denoted by T.
In the event that a great decrease in the level count value occurs, even by sending out a packet and adding the packet length to the level count value, the level count value cannot be returned to a level higher than the threshold value and the condition for outputting packets remains satisfied. In this case, burst transmission of a plurality of packets belonging to the same flow occurs, as denoted by P4, P5, P6, P7, and packet transfer that temporarily exceeds the maximum allowed bandwidth is possible to occur until the level count value increases to a level sufficiently higher than the threshold value again.